/**
 * 42. 接雨水
 * https://leetcode-cn.com/problems/trapping-rain-water/
 */

/**
 * @param {number[]} heights
 * @return {number}
 */
function trap(heights) {
  const { length } = heights;
  if (length < 3) return 0;
  const lastIndex = length - 1;
  const leftMaxes = new Array(length);
  const rightMaxes = new Array(length);
  let leftMax = heights[0];
  let rightMax = heights[lastIndex];
  for (let i = 1; i < lastIndex; i += 1) {
    leftMaxes[i] = leftMax;
    const height = heights[i];
    if (height > leftMax) {
      leftMax = height;
    }
  }
  for (let i = lastIndex - 1; i > 0; i -= 1) {
    rightMaxes[i] = rightMax;
    const height = heights[i];
    if (height > rightMax) {
      rightMax = height;
    }
  }
  let total = 0;
  for (let i = 1; i < lastIndex; i += 1) {
    leftMax = leftMaxes[i];
    rightMax = rightMaxes[i];
    const height = heights[i];
    if (leftMax > height && rightMax > height) {
      total += (Math.min(leftMax, rightMax) - height);
    }
  }
  return total;
}

console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) === 6);
console.log(trap([4, 2, 0, 3, 2, 5]) === 9);
